package 动态规划.背包And分组And切割问题系列;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/1 15:23
 */
public class leetcode6169分割字符串不超过k {

    public static void main(String[] args) {

//        String s = "1829727651";
//        String s = "165462";
        String s = "7614953199576414777";
        System.out.println(s.length());
        int k = 16;
        System.out.println(solution(s, k));

    }
/*
 从这个 debug 的 过程中， 你学会了 什么
 1. 最主要的就是，思路不清晰
 2. 边界情况考虑不周到！
 */

    public static  int solution(String s,int k){
        String kNumber = k + "";
        if(s.length() < kNumber.length() || s.equals(kNumber)) {
            return 1;
        }
        int len = s.length();
        int dp[] = new int [ len + 1];
//        int recursion = recursion(0, s,kNumber ,s.length(),dp);
        int recursion = recursion(0, s,k ,kNumber.length(),s.length(),dp);
        return recursion == s.length() + 1 ? -1 : recursion;
    }

    /*
    进行一个，对内层for 循环的优化，
    可以对这个for 循环的范围进行优化
    时间 复杂度 O（N * kLen） 但是 kLen max = 10
    所以时间复杂度 O（10 * N） = O（N）
    最优解是严格的 O（N）
     */
    public static int recursion(int index,String s,int k,int kLen,int sLen,int []dp){
        if(index == sLen){
            return 0;
        }
        if(dp[index] != 0){
            return dp[index];
        }
        int ans = sLen + 1;
        // 防止 int 溢出， 这里使用 long
        long temp = 0;
//        "7614953199576414777"
        for(int i = 1; i <= kLen && index + i <= sLen;i++){
            /*
            这里比较的方式，就比较的多了，
            我们可以 用  s.substring(index,index + i)
            截取的方式 ，来进行比较， 或者 使用 ，一个  temp 变量 记录， 来比较
            都可以
             */
            // 编码的细节 ，这里 之前写的是  s.charAt(index) - '0' 这不 明显的错误！
            temp = temp * 10 + s.charAt(index + i - 1) - '0';
            if(temp <= k){
                System.out.print(temp + " ");
                ans = Math.min(ans,recursion(index + i,s,k,kLen,sLen,dp) + 1);
            }

        }
        return dp[index] = ans;
    }



    /*
     下面这个 常数时间复杂度 有点高！
     */
    public static int recursion(int index,String s,String kNumber, int len,int [] dp){
        if(index == len){
            return dp[index] = 0;
        }
        if(dp[index] != 0)
            return dp[index];
        int ans = len + 1;
        for(int i = index;  i - index + 1 <= kNumber.length() && i < len && Integer.parseInt(s.substring(index,i + 1)) <= Integer.parseInt(kNumber);i++){
//            System.out.print(s.substring(index,i + 1) + " ");
            ans = Math.min(ans,recursion(i + 1,s,kNumber,len,dp) + 1);
        }
        return dp[index] = ans;
    }
/*
    有点 贪心的 的 味道
    仔细的分析清楚题
    O(N)
 */
    public int minimumPartition(String s, int k) {
        int count = 0;
        for (int i = 0; i < s.length(); count++) {
            if (s.charAt(i) - '0' > k) {
                return -1;
            }
            for (long curr = 0; i < s.length() && (curr = curr * 10 + s.charAt(i) - '0') <= k; i++) {
            }
        }
        return count;
    }


}
